home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / circuits / irsim-ca.2 / irsim-ca / irsim-cap-9.2 / src / other / h2a / sort.c < prev   
C/C++ Source or Header  |  1991-02-25  |  3KB  |  182 lines
  1. #include "history.h"
  2.  
  3.  
  4. #define    BIT8        0xff
  5. #define    BIT12        0xfff
  6. #define    BIT24        0xffffff
  7.  
  8. #define    CNTSIZE        ( 4096 + 4096 + 256 )
  9. #define    COUNT1        &countBuff[ 0 ]
  10. #define    COUNT2        &countBuff[ 4096 ]
  11. #define    COUNT3        &countBuff[ 4096 + 4096 ]
  12. #define    ENDCNT        &countBuff[ CNTSIZE ]
  13.  
  14.  
  15. static    int    *countBuff;
  16. static  phist    *data_;
  17. static    phist    *dataBuff;
  18. static    phist    *dataBuff1;
  19.  
  20.  
  21. /*
  22.  * Sort the edge array pointed to by 'lineBuff'.  Return a pointer to a
  23.  * sorted array of pointers into the original data.
  24.  */
  25. phist *Sort( nlines, lineBuff, maxv )
  26.   int    nlines;
  27.   phist  *lineBuff;
  28.   long   maxv;
  29.   {
  30.     phist  *tmp;
  31.  
  32.     data_ = lineBuff;
  33.     dataBuff = tmp = (phist *) malloc( sizeof( phist ) * nlines );
  34.     countBuff = (int *) malloc( sizeof( int ) * CNTSIZE );
  35.     dataBuff1 = (phist *) malloc( sizeof( phist ) * nlines );
  36.     BucketSort( nlines, maxv );
  37.     if( dataBuff != tmp )            /* swapped by sort */
  38.       {
  39.     register phist    *src, *dst, *end;
  40.     
  41.     dataBuff1 = dataBuff;
  42.     dataBuff = tmp;
  43.     src = dataBuff1;
  44.     dst = dataBuff;
  45.     end = &dataBuff1[ nlines ];
  46.     do { *dst++ = *src++; } while( src < end );
  47.       }
  48.     return( dataBuff );
  49.   }
  50.  
  51.  
  52. static BucketSort( nlines, maxv )
  53.   int   nlines;
  54.   long  maxv;
  55.   {
  56.    {
  57.     register int    *cp, *end;
  58.  
  59.     cp = COUNT1;
  60.     end = ENDCNT;
  61.     do { *cp++ = 0; } while( cp < end );
  62.    }
  63.  
  64.    {
  65.     register phist    *dat, *end;
  66.     register int    *count1, *count2, *count3;
  67.  
  68.     count1 = COUNT1;
  69.     count2 = COUNT2;
  70.     count3 = COUNT3;
  71.     dat = data_;
  72.     end = &data_[ nlines ];
  73.  
  74.     if( maxv <= BIT12 )
  75.       {
  76.     do
  77.       {
  78.         count1[ (*dat)->time & BIT12 ]++;
  79.         dat++;
  80.       }
  81.     while( dat < end );
  82.       }
  83.     else if( maxv <= BIT24 )
  84.       {
  85.     do
  86.       {
  87.         count1[ (*dat)->time & BIT12 ]++;
  88.         count2[ ( (*dat)->time >> 12 ) & BIT12 ]++;
  89.         dat++;
  90.       }
  91.     while( dat < end );
  92.       }
  93.     else
  94.       {
  95.     do
  96.       {
  97.         count1[ (*dat)->time & BIT12 ]++;
  98.         count2[ ( (*dat)->time >> 12 ) & BIT12 ]++;
  99.         count3[ ( (*dat)->time >> 24 ) & BIT8 ]++;
  100.         dat++;
  101.       }
  102.     while( dat < end );
  103.       }
  104.    }
  105.  
  106.    {
  107.     register int    *cp, *cp_1;
  108.     register int    *cp2, *cp2_1;
  109.     register int    *end;
  110.     cp = COUNT1;
  111.     cp_1 = &cp[1];
  112.     cp2 = COUNT2;
  113.     cp2_1 = &cp2[1];
  114.     end = COUNT2;
  115.     do
  116.       {
  117.     *cp_1++ += *cp++;
  118.     *cp2_1++ += *cp2++;
  119.       }
  120.     while( cp_1 < end );
  121.     
  122.     cp = COUNT3;
  123.     cp_1 = &cp[1];
  124.     end = ENDCNT;
  125.     do { *cp_1++ += *cp++; } while( cp_1 < end );
  126.    }
  127.  
  128.    {
  129.     register int    tmp;
  130.     register int    *count;
  131.     register phist    *dat;
  132.     register phist    *datPtr, *end;
  133.     
  134.     dat = &data_[ nlines-1 ];
  135.     count = COUNT1;
  136.     datPtr = dataBuff;
  137.     do
  138.       {
  139.     tmp = --count[ (*dat)->time & BIT12 ];
  140.     datPtr[ tmp ] = (*dat);
  141.     dat--;
  142.       }
  143.     while( dat >= data_ );
  144.     
  145.     if( maxv <= BIT12 )
  146.     goto done;
  147.  
  148.     datPtr = &dataBuff[ nlines-1 ];
  149.     end = dataBuff;
  150.     count = COUNT2;
  151.     do
  152.       {
  153.     tmp = -- count[ ((*datPtr)->time >> 12) & BIT12 ];
  154.     dataBuff1[ tmp ] = *datPtr;
  155.     datPtr--;
  156.       }
  157.     while( datPtr >= end );
  158.  
  159.     if( maxv <= BIT24 )
  160.       {
  161.     datPtr = dataBuff1;
  162.     dataBuff1 = dataBuff;
  163.     dataBuff = datPtr;
  164.     goto done;
  165.       }
  166.  
  167.     datPtr = &dataBuff1[ nlines-1 ];
  168.     end = dataBuff1;
  169.     count = COUNT3;
  170.     do
  171.       {
  172.     tmp = -- count[ ((*datPtr)->time >> 24) & BIT8 ];
  173.     dataBuff[ tmp ] = *datPtr;
  174.     datPtr--;
  175.       }
  176.     while( datPtr >= end );
  177.  
  178.    }
  179.  
  180.   done : ;
  181.   }
  182.